<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
    "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
  <title>Exception-Safety in Generic Components</title>
  <meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
  <link rel="icon" href="/favicon.ico" type="image/ico" />
  <link rel="stylesheet" type="text/css" href=
  "/style-v2/section-community.css" />
  <!--[if IE 7]> <style type="text/css"> body { behavior: url(/style-v2/csshover3.htc); } </style> <![endif]-->

  <style type="text/css">
/*<![CDATA[*/
  h3.c2 {text-align: center}
  p.c1 {font-style: italic; text-align: center}
  /*]]>*/
  </style>
</head><!--
Note: Editing website content is documented at:
https://www.boost.org/development/website_updating.html
-->

<body>
  <div id="heading">
    <!--#include virtual="/common/heading.html" -->
  </div>

  <div id="body">
    <div id="body-inner">
      <div id="content">
        <div class="section" id="intro">
          <div class="section-0">
            <div class="section-title">
              <h1>Exception-Safety in Generic Components</h1>
            </div>

            <div class="section-body">
              <p class="c1"><strong>Lessons Learned from Specifying
              Exception-Safety for the C++ Standard Library</strong></p>

              <h3 class="c2"><a href="http://daveabrahams.com">David Abrahams</a></h3>

              <h3 class="c2"><a href=
              "mailto:dave@boostpro.com">dave@boostpro.com</a></h3>

              <p><strong>Abstract.</strong> This paper represents the
              knowledge accumulated in response to a real-world need: that
              the C++ Standard Template Library exhibit useful and
              well-defined interactions with exceptions, the error-handling
              mechanism built-in to the core C++ language. It explores the
              meaning of exception-safety, reveals surprising myths about
              exceptions and genericity, describes valuable tools for
              reasoning about program correctness, and outlines an automated
              testing procedure for verifying exception-safety.</p>

              <p><strong>Keywords:</strong> exception-safety, exceptions,
              STL, C++</p>

              <h2>1 What is exception-safety?</h2>

              <p>Informally, exception-safety in a component means that it
              exhibits reasonable behavior when an exception is thrown during
              its execution. For most people, the term
              &ldquo;reasonable&rdquo; includes all the usual expectations
              for error-handling: that resources should not be leaked, and
              that the program should remain in a well-defined state so that
              execution can continue. For most components, it also includes
              the expectation that when an error is encountered, it is
              reported to the caller.</p>

              <p>More formally, we can describe a component as minimally
              exception-safe if, when exceptions are thrown from within that
              component, its invariants are intact. Later on we'll see that
              at least three different levels of exception-safety can be
              usefully distinguished. These distinctions can help us to
              describe and reason about the behavior of large systems.</p>

              <p>In a generic component, we usually have an additional
              expectation of <i>exception-neutrality</i>, which means that
              exceptions thrown by a component's type parameters should be
              propagated, unchanged, to the component's caller.</p>

              <h2>2 Myths and Superstitions</h2>

              <p>Exception-safety seems straightforward so far: it doesn't
              constitute anything more than we'd expect from code using more
              traditional error-handling techniques. It might be worthwhile,
              however, to examine the term from a psychological viewpoint.
              Nobody ever spoke of &ldquo;error-safety&rdquo; before C++ had
              exceptions.</p>

              <p>It's almost as though exceptions are viewed as a
              <i>mysterious attack</i> on otherwise correct code, from which
              we must protect ourselves. Needless to say, this doesn't lead
              to a healthy relationship with error handling! During
              standardization, a democratic process which requires broad
              support for changes, I encountered many widely-held
              superstitions. In order to even begin the discussion of
              exception-safety in generic components, it may be worthwhile
              confronting a few of them.</p>

              <p><i>&ldquo;Interactions between templates and exceptions are
              not well-understood.&rdquo;</i> This myth, often heard from
              those who consider these both new language features, is easily
              disposed of: there simply are no interactions. A template, once
              instantiated, works in all respects like an ordinary class or
              function. A simple way to reason about the behavior of a
              template with exceptions is to think of how a specific
              instantiation of that template works. Finally, the genericity
              of templates should not cause special concern. Although the
              component's client supplies part of the operation (which may,
              unless otherwise specified, throw arbitrary exceptions), the
              same is true of operations using familiar virtual functions or
              simple function pointers.</p>

              <p><i>&ldquo;It is well known to be impossible to write an
              exception-safe generic container.&rdquo;</i> This claim is
              often heard with reference to an article by Tom Cargill
              <a title=
              "Tom Cargill, &ldquo;Exception Handling: A False Sense of Security&rdquo;, C++ Report, Nov-Dec 1994"
              href="#reference4"><sup>[4]</sup></a> in which he explores the
              problem of exception-safety for a generic stack template. In
              his article, Cargill raises many useful questions, but
              unfortunately fails to present a solution to his
              problem.<a title=
              "Probably the greatest impediment to a solution in Cargill's case was an unfortunate combination of choices on his part: the interface he chose for his container was incompatible with his particular demands for safety. By changing either one he might have solved the problem."
              href="#footnote1"><sup>1</sup></a> He concludes by suggesting
              that a solution may not be possible. Unfortunately, his article
              was read by many as &ldquo;proof&rdquo; of that speculation.
              Since it was published there have been many examples of
              exception-safe generic components, among them the C++ standard
              library containers.</p>

              <p><i>&ldquo;Dealing with exceptions will slow code down, and
              templates are used specifically to get the best possible
              performance.&rdquo;</i> A good implementation of C++ will not
              devote a single instruction cycle to dealing with exceptions
              until one is thrown, and then it can be handled at a speed
              comparable with that of calling a function <a title=
              "Bjarne Stroustrup, The Design And Evolution of C++. Addison Wesley, Reading, MA, 1995, ISBN 0-201-54330-3, Section 16.9.1."
              href="#reference7"><sup>[7]</sup></a>. That alone gives
              programs using exceptions performance equivalent to that of a
              program which ignores the possibility of errors. Using
              exceptions can actually result in faster programs than
              &ldquo;traditional&rdquo; error handling methods for other
              reasons. First, a catch block clearly indicates to the compiler
              which code is devoted to error-handling; it can then be
              separated from the usual execution path, improving locality of
              reference. Second, code using &ldquo;traditional&rdquo; error
              handling must typically test a return value for errors after
              every single function call; using exceptions completely
              eliminates that overhead.</p>

              <p><i>&ldquo;Exceptions make it more difficult to reason about
              a program's behavior.&rdquo;</i> Usually cited in support of
              this myth is the way &ldquo;hidden&rdquo; execution paths are
              followed during stack-unwinding. Hidden execution paths are
              nothing new to any C++ programmer who expects local variables
              to be destroyed upon returning from a function:</p>
              <pre>
ErrorCode f( int&amp; result )         // 1 
{                                  // 2 
    X x;                           // 3 
    ErrorCode err = x.g( result ); // 4 
    if ( err != kNoError )         // 5 
        return err;                // 6 
    // ...More code here... 
    return kNoError;               // 7 
}
</pre>

              <p>In the example above, there is a &ldquo;hidden&rdquo; call
              to <code>X::~X()</code> in lines 6 and 7. Granted, using
              exceptions, there is no code devoted to error handling
              visible:</p>
              <pre>
int f()                 // 1 
{                       // 2 
    X x;                // 3 
    int result = x.g(); // 4 
    // ...More code here... 
    return result;      // 5 
} 
</pre>

              <p>For many programmers more familiar with exceptions, the
              second example is actually more readable and understandable
              than the first. The &ldquo;hidden&rdquo; code paths include the
              same calls to destructors of local variables. In addition, they
              follow a simple pattern which acts <i>exactly</i> as though
              there were a potential return statement after each function
              call in case of an exception. Readability is enhanced because
              the normal path of execution is unobscured by error-handling,
              and return values are freed up to be used in a natural way.</p>

              <p>There is an even more important way in which exceptions can
              enhance correctness: by allowing simple class invariants. In
              the first example, if <code>x</code>'s constructor should need
              to allocate resources, it has no way to report a failure: in
              C++, constructors have no return values. The usual result when
              exceptions are avoided is that classes requiring resources must
              include a separate initializer function which finishes the job
              of construction. The programmer can therefore never be sure,
              when an object of class <code>X</code> is used, whether he is
              handling a full-fledged <code>X</code> or some abortive attempt
              to construct one (or worse: someone simply forgot to call the
              initializer!)</p>

              <h2>3 A contractual basis for exception-safety</h2>

              <p>A non-generic component can be described as exception-safe
              in isolation, but because of its configurability by client
              code, exception-safety in a generic component usually depends
              on a contract between the component and its clients. For
              example, the designer of a generic component might require that
              an operation which is used in the component's destructor not
              throw any exceptions.<a title=
              " It is usually inadvisable to throw an exception from a destructor in C++, since the destructor may itself be called during the stack-unwinding caused by another exception. If the second exception is allowed to propagate beyond the destructor, the program is immediately terminated."
              href="#footnote2"><sup>2</sup></a> The generic component might,
              in return, provide one of the following guarantees:</p>

              <ul>
                <li>The <i>basic</i> guarantee: that the invariants of the
                component are preserved, and no resources are leaked.</li>

                <li>The <i>strong</i> guarantee: that the operation has
                either completed successfully or thrown an exception, leaving
                the program state exactly as it was before the operation
                started.</li>

                <li>The <i>no-throw</i> guarantee: that the operation will
                not throw an exception.</li>
              </ul>

              <p>The basic guarantee is a simple minimum standard for
              exception-safety to which we can hold all components. It says
              simply that after an exception, the component can still be used
              as before. Importantly, the preservation of invariants allows
              the component to be destroyed, potentially as part of
              stack-unwinding. This guarantee is actually less useful than it
              might at first appear. If a component has many valid states,
              after an exception we have no idea what state the component is
              in; only that the state is valid. The options for recovery in
              this case are limited: either destruction or resetting the
              component to some known state before further use. Consider the
              following example:</p>
              <pre>
template &lt;class X&gt; 
void print_random_sequence() 
{ 
    std::vector&lt;X&gt; v(10); // A vector of 10 items 
    try { 
        // Provides only the <i>basic</i> guarantee 
        v.insert( v.begin(), X() ); 
    } 
    catch(...) {} // ignore any exceptions above 
    // print the vector's contents 
    std::cout "(" &lt;&lt; v.size() &lt;&lt; ") "; 
    std::copy( v.begin(), v.end(), 
    std::ostream_iterator&lt;X&gt;( std::cout, " " ) ); 
} 
</pre>

              <p>Since all we know about v after an exception is that it is
              valid, the function is allowed to print any random sequence of
              <code>X</code>s.<a title=
              "In practice of course, this function would make an extremely poor random sequence generator!"
              href="#footnote3"><sup>3</sup></a> It is &ldquo;safe&rdquo; in
              the sense that it is not allowed to crash, but its output may
              be unpredictable.</p>

              <p>The <i>strong</i> guarantee provides full
              &ldquo;commit-or-rollback&rdquo; semantics. In the case of C++
              standard containers, this means, for example, that if an
              exception is thrown all iterators remain valid. We also know
              that the container has exactly the same elements as before the
              exception was thrown. A transaction that has no effects if it
              fails has obvious benefits: the program state is simple and
              predictable in case of an exception. In the C++ standard
              library, nearly all of the operations on the node-based
              containers list, set, multiset, map, and multimap provide the
              <i>strong</i> guarantee.<a title=
              "It is worth noting that mutating algorithms usually cannot provide the strong guarantee: to roll back a modified element of a range, it must be set back to its previous value using operator=, which itself might throw. In the C++ standard library, there are a few exceptions to this rule, whose rollback behavior consists only of destruction: uninitialized_copy, uninitialized_fill, and uninitialized_fill_n."
              href="#footnote4"><sup>4</sup></a>).</p>

              <p>The <i>no-throw</i> guarantee is the strongest of all, and
              it says that an operation is guaranteed not to throw an
              exception: it always completes successfully. This guarantee is
              necessary for most destructors, and indeed the destructors of
              C++ standard library components are all guaranteed not to throw
              exceptions. The <i>no-throw</i> guarantee turns out to be
              important for other reasons, as we shall see.<a title=
              "All type parameters supplied by clients of the C++ standard library are required not to throw from their destructors. In return, all components of the C++ standard library provide at least the basic guarantee."
              href="#footnote5"><sup>5</sup></a></p>

              <h2>4 Legal Wrangling</h2>

              <p>Inevitably, the contract can get more complicated: a quid
              pro quo arrangement is possible. Some components in the C++
              Standard Library give one guarantee for arbitrary type
              parameters, but give a stronger guarantee in exchange for
              additional promises from the client type that no exceptions
              will be thrown. For example, the standard container operation
              <code>vector&lt;T&gt;::erase</code> gives the <i>basic</i>
              guarantee for any <code>T</code>, but for types whose copy
              constructor and copy assignment operator do not throw, it gives
              the <i>no-throw</i> guarantee.<a title=
              "Similar arrangements might have been made in the C++ standard for many of the mutating algorithms, but were never considered due to time constraints on the standardization process."
              href="#footnote6"><sup>6</sup></a></p>

              <h2>5 What level of exception-safety should a component
              specify?</h2>

              <p>From a client's point-of-view, the strongest possible level
              of safety would be ideal. Of course, the <i>no-throw</i>
              guarantee is simply impossible for many operations, but what
              about the <i>strong</i> guarantee? For example, suppose we
              wanted atomic behavior for
              <code>vector&lt;T&gt;::insert</code>. Insertion into the middle
              of a vector requires copying elements after the insertion point
              into later positions, to make room for the new element. If
              copying an element can fail, rolling back the operation would
              require &ldquo;undoing&rdquo; the previous copies...which
              depends on copying again. If copying back should fail (as it
              likely would), we have failed to meet our guarantee.</p>

              <p>One possible alternative would be to redefine
              <code>insert</code> to build the new array contents in a fresh
              piece of memory each time, and only destroy the old contents
              when that has succeeded. Unfortunately, there is a non-trivial
              cost if this approach is followed: insertions near the end of a
              vector which might have previously caused only a few copies
              would now cause every element to be copied. The <i>basic</i>
              guarantee is a &ldquo;natural&rdquo; level of safety for this
              operation, which it can provide without violating its
              performance guarantees. In fact all of the operations in the
              library appear to have such a &ldquo;natural&rdquo; level of
              safety.</p>

              <p>Because performance requirements were already a
              well-established part of the draft standard and because
              performance is a primary goal of the STL, there was no attempt
              to specify more safety than could be provided within those
              requirements. Although not all of the library gives the
              <i>strong</i> guarantee, almost any operation on a standard
              container which gives the <i>basic</i> guarantee can be made
              <i>strong</i> using the &ldquo;make a new copy&rdquo; strategy
              described above:</p>
              <pre>
template &lt;class Container, class BasicOp&gt; 
void MakeOperationStrong( Container&amp; c, const BasicOp&amp; op ) 
{ 
    Container tmp(c); // Copy c 
    op(tmp); // Work on the copy 
    c.swap(tmp); // Cannot fail<a title=
"Associative containers whose Compare object might throw an exception when copied cannot use this technique, since the swap function might fail."
href="#footnote7"><sup>7</sup></a>
}
</pre>

              <p>This technique can be folded into a wrapper class to make a
              similar container which provides stronger guarantees (and
              different performance characteristics).<a title=
              "This suggests another potential use for the oft-wished-for but as yet unseen container traits&lt;&gt; template: automated container selection to meet exceptionsafety constraints."
              href="#footnote8"><sup>8</sup></a></p>

              <h2>6 Should we take everything we can get?</h2>

              <p>By considering a particular implementation, we can hope to
              discern a natural level of safety. The danger in using this to
              establish requirements for a component is that the
              implementation might be restricted. If someone should come up
              with a more-efficient implementation which we'd like to use, we
              may find that it's incompatible with our exception-safety
              requirements. One might expect this to be of no concern in the
              well-explored domains of data structures and algorithms covered
              by the STL, but even there, advances are being made. A good
              example is the recent <i>introsort</i> algorithm <a title=
              "D. R. Musser, &ldquo;Introspective Sorting and Selection Algorithms&rdquo;, Software-Practice and Experience 27(8):983-993, 1997."
              href="#reference6"><sup>[6]</sup></a>, which represents a
              substantial improvement in worst-case complexity over the
              well-established <i>quicksort</i>.</p>

              <p>To determine exactly how much to demand of the standard
              components, I looked at a typical real-world scenario. The
              chosen test case was a &ldquo;composite container.&rdquo; Such
              a container, built of two or more standard container
              components, is not only commonly needed, but serves as a simple
              representative case for maintaining invariants in larger
              systems:</p>
              <pre>
// SearchableStack - A stack which can be efficiently searched 
// for any value. 
template &lt;class T&gt; 
class SearchableStack 
{ 
 public: 
    void push(const T&amp; t); // O(log n) 
    void pop(); // O(log n) 
    bool contains(const T&amp; t) const; // O(log n) 
    const T&amp; top() const; // O(1) 
 private: 
    std::set&lt;T&gt; set_impl; 
    std::list&lt;std::set&lt;T&gt;::iterator&gt; list_impl; 
}; 
</pre>

              <p>The idea is that the list acts as a stack of set iterators:
              every element goes into the set first, and the resulting
              position is pushed onto the list. The invariant is
              straightforward: the set and the list should always have the
              same number of elements, and every element of the set should be
              referenced by an element of the list. The following
              implementation of the push function is designed to give the
              <i>strong</i> guarantee within the natural levels of safety
              provided by set and list:</p>
              <pre>
template &lt;class T&gt;                                // 1 
void SearchableStack&lt;T&gt;::push(const T&amp; t)         // 2 
{                                                       // 3 
    set&lt;T&gt;::iterator i = set_impl.insert(t);      // 4 
    try                                                 // 5 
    {                                                   // 6 
        list_impl.push_back(i);                         // 7 
    }                                                   // 8 
    catch(...)                                          // 9 
    {                                                   // 10 
        set_impl.erase(i);                              // 11 
        throw;                                          // 12 
    }                                                   // 13 
}                                                       // 14 
</pre>

              <p>What does our code actually require of the library? We need
              to examine the lines where non-const operations occur:</p>

              <ul>
                <li>Line 4: if the insertion fails but <code>set_impl</code>
                is modified in the process, our invariant is violated. We
                need to be able to rely on the <i>strong</i> guarantee from
                <code>set&lt;T&gt;::insert</code>.</li>

                <li>Line 7: likewise, if <code>push_back</code> fails, but
                <code>list_impl</code> is modified in the process, our
                invariant is violated, so we need to be able to rely on the
                <i>strong</i> guarantee from list&lt;T&gt;::insert.</li>

                <li>Line 11: here we are &ldquo;rolling back&rdquo; the
                insertion on line 4. If this operation should fail, we will
                be unable to restore our invariant. We absolutely depend on
                the <i>no-throw</i> guarantee from
                <code>set&lt;T&gt;::erase</code>.<a title=
                "One might be tempted to surround the erase operation with a try/catch block to reduce the requirements on set&lt;T&gt; and the problems that arise in case of an exception, but in the end that just begs the question. First, erase just failed and in this case there are no viable alternative ways to produce the necessary result. Second and more generally, because of the variability of its type parameters a generic component can seldom be assured that any alternatives will succeed."
                href="#footnote9"><sup>9</sup></a></li>

                <li>Line 11: for the same reasons, we also depend on being
                able to pass the <code>i</code> to the <code>erase</code>
                function: we need the <i>no-throw</i> guarantee from the copy
                constructor of <code>set&lt;T&gt;::iterator</code>.</li>
              </ul>

              <p>I learned a great deal by approaching the question this way
              during standardization. First, the guarantee specified for the
              composite container actually depends on stronger guarantees
              from its components (the <i>no-throw</i> guarantees in line
              11). Also, I took advantage of all of the natural level of
              safety to implement this simple example. Finally, the analysis
              revealed a requirement on iterators which I had previously
              overlooked when operations were considered on their own. The
              conclusion was that we should provide as much of the natural
              level of safety as possible. Faster but less-safe
              implementations could always be provided as extensions to the
              standard components. <sup><a title=
              "The prevalent philosophy in the design of STL was that functionality that wasn't essential to all uses should be left out in favor of efficiency, as long as that functionality could be obtained when needed by adapting the base components. This departs from that philosophy, but it would be difficult or impossible to obtain even the basic guarantee by adapting a base component that doesn't already have it."
              href="#footnote10">10</a></sup></p>

              <h2>7 Automated testing for exception-safety</h2>

              <p>As part of the standardization process, I produced an
              exception-safe reference implementation of the STL.
              Error-handling code is seldom rigorously tested in real life,
              in part because it is difficult to cause error conditions to
              occur. It is very common to see error-handling code which
              crashes the first time it is executed ...in a shipping product!
              To bolster confidence that the implementation actually worked
              as advertised, I designed an automated test suite, based on an
              exhaustive technique due to my colleague Matt Arnold.</p>

              <p>The test program started with the basics: reinforcement and
              instrumentation, especially of the global operators
              <code>new</code> and <code>delete</code>.<sup><a title=
              "An excellent discussion on how to fortify memory subsystems can be found in: Steve Maguire, Writing Solid Code, Microsoft Press, Redmond, WA, 1993, ISBN 1-55615- 551-4."
              href="#footnote11">11</a></sup>Instances of the components
              (containers and algorithms) were created, with type parameters
              chosen to reveal as many potential problems as possible. For
              example, all type parameters were given a pointer to
              heap-allocated memory, so that leaking a contained object would
              be detected as a memory leak.</p>

              <p>Finally, a scheme was designed that could cause an operation
              to throw an exception at each possible point of failure. At the
              beginning of every client-supplied operation which is allowed
              to throw an exception, a call to <code>ThisCanThrow</code> was
              added. A call to <code>ThisCanThrow</code> also had to be added
              everywhere that the generic operation being tested might throw
              an exception, for example in the global operator
              <code>new</code>, for which an instrumented replacement was
              supplied.</p>
              <pre>
// Use this as a type parameter, e.g. vector&lt;TestClass&gt; 
struct TestClass 
{ 
    TestClass( int v = 0 ) 
        : p( ThisCanThrow(), new int( v ) ) {} 
    TestClass( const TestClass&amp; rhs ) 
        : p( ThisCanThrow(), new int( *rhs.p ) ) {} 
    const TestClass&amp; operator=( const TestClass&amp; rhs ) 
        { ThisCanThrow(); *p = *rhs.p; } 
    bool operator==( const TestClass&amp; rhs ) const
        { ThisCanThrow(); return *p == *rhs.p; } 
    ...etc... 
    ~TestClass() { delete p; } 
};
</pre>

              <p><code>ThisCanThrow</code> simply decrements a &ldquo;throw
              counter&rdquo; and, if it has reached zero, throws an
              exception. Each test takes a form which begins the counter at
              successively higher values in an outer loop and repeatedly
              attempts to complete the operation being tested. The result is
              that the operation throws an exception at each successive step
              along its execution path that can possibly fail. For example,
              here is a simplified version of the function used to test the
              <i>strong</i> guarantee: <a title=
              "Note that this technique requires that the operation being tested be exception-neutral. If the operation ever tries to recover from an exception and proceed, the throw counter will be negative, and subsequent operations that might fail will not be tested for exception-safety."
              href="#footnote12"><sup>12</sup></a></p>
              <pre>
extern int gThrowCounter; // The throw counter
void ThisCanThrow() 
{ 
    if (gThrowCounter-- == 0) 
        throw 0; 
} 
 
template &lt;class Value, class Operation&gt; 
void StrongCheck(const Value&amp; v, const Operation&amp; op) 
{ 
    bool succeeded = false; 
    for (long nextThrowCount = 0; !succeeded; ++nextThrowCount) 
    { 
        Value duplicate = v; 
        try 
        { 
            gThrowCounter = nextThrowCount; 
            op( duplicate ); // Try the operation 
            succeeded = true; 
        } 
        catch(...) // Catch all exceptions 
        { 
            bool unchanged = duplicate == v; // Test <i>strong</i> guarantee 
            assert( unchanged ); 
        } 
        // Specialize as desired for each container type, to check 
        // integrity. For example, size() == distance(begin(),end()) 
        CheckInvariant(v); // Check any invariant 
    } 
}
</pre>

              <p>Notably, this kind of testing is much easier and less
              intrusive with a generic component than with non-generics,
              because testing-specific type parameters can be used without
              modifying the source code of the component being tested. Also,
              generic functions like <code>StrongCheck</code> above were
              instrumental in performing the tests on a wide range of values
              and operations.</p>

              <h2>8 Further Reading</h2>

              <p>To my knowledge, there are currently only two descriptions
              of STL exception-safety available. The original specification
              <a title="D. Abrahams, Exception Safety in STLport" href=
              "#reference2"><sup>[2]</sup></a> for the reference
              exception-safe implementation of the STL is an informal
              specification, simple and self-explanatory (also verbose), and
              uses the <i>basic-</i> and <i>strong-</i>guarantee distinctions
              outlined in this article. It explicitly forbids leaks, and
              differs substantively from the final C++ standard in the
              guarantees it makes, though they are largely identical. I hope
              to produce an updated version of this document soon.</p>

              <p>The description of exception-safety in the C++ Standard
              <a title=
              "International Standard ISO/IEC 14882, Information Technology-Programming Languages-C++, Document Number ISO/IEC 14882-1998"
              href="#reference1"><sup>[1]</sup></a> is only slightly more
              formal, but relies on hard-to-read &ldquo;standardese&rdquo;
              and an occasionally subtle web of implication.<a title=
              "The changes to the draft standard which introduced exception-safety were made late in the process, when amendments were likely to be rejected solely on the basis of the number of altered words. Unfortunately, the result compromises clarity somewhat in favor of brevity. Greg Colvin was responsible for the clever language-lawyering needed to minimize the extent of these changes."
              href="#footnote13"><sup>13</sup></a> In particular, leaks are
              not treated directly at all. It does have the advantage that it
              <i>is</i> the standard.</p>

              <p>The original reference implementation <a title=
              "B. Fomitchev, Adapted SGI STL Version 1.0, with exception handling code by D. Abrahams"
              href="#reference5"><sup>[5]</sup></a> of the exception-safe STL
              is an adaptation of an old version of the SGI STL, designed for
              C++ compilers with limited features. Although it is not a
              complete STL implementation, the code may be easier to read,
              and it illustrates a useful base-class technique for
              eliminating exception-handling code in constructors. The full
              test suite <a title=
              "D. Abrahams and B. Fomitchev, Exception Handling Test Suite"
              href="#reference3"><sup>[3]</sup></a> used to validate the
              reference implementation has been used successfully to validate
              all recent versions of the SGI STL, and has been adapted to
              test one other vendor's implementation (which failed). As noted
              on the documentation page, it also seems to have the power to
              reveal hidden compiler bugs, particularly where optimizers
              interact with exception-handling code.</p>

              <h2>References</h2>

              <ol>
                <li><a name="reference1" id="reference1">International</a>
                Standard ISO/IEC 14882, <i>Information Technology-Programming
                Languages-C++</i>, Document Number ISO/IEC 14882-1998,
                available from <a href=
                "http://webstore.ansi.org/ansidocstore/default.asp">http://webstore.ansi.org/ansidocstore/default.asp</a>.</li>

                <li><a name="reference2" id="reference2">D.</a> Abrahams,
                <i>Exception Safety in STLport</i>, available at <a href=
                "http://www.stlport.org/doc/exception_safety.html">http://www.stlport.org/doc/exception_safety.html</a>.</li>

                <li><a name="reference3" id="reference3">D.</a> Abrahams and
                B. Fomitchev, <i>Exception Handling Test Suite</i>, available
                at <a href=
                "http://www.stlport.org/doc/eh_testsuite.html">http://www.stlport.org/doc/eh_testsuite.html</a>.</li>

                <li><a name="reference4" id="reference4">Tom</a> Cargill,
                &ldquo;Exception Handling: A False Sense of Security,&rdquo;
                C++ Report, Nov-Dec 1994, also available at <a href=
                "http://www.informit.com/content/images/020163371x/supplements/Exception_Handling_Article.html">
                http://www.awprofessional.com/content/images/020163371x/supplements/Exception_Handling_Article.html</a>.</li>

                <li><a name="reference5" id="reference5">B.</a> Fomitchev,
                <i>Adapted SGI STL Version 1.0</i>, with exception handling
                code by D. Abrahams, available at <a href=
                "http://www.stlport.org">http://www.stlport.org</a>.</li>

                <li><a name="reference6" id="reference6">D.</a> R. Musser,
                &ldquo;Introspective Sorting and Selection Algorithms,&rdquo;
                <i>Software-Practice and Experience</i> 27(8):983-993,
                1997.</li>

                <li><a name="reference7" id="reference7">Bjarne</a>
                Stroustrup, <i>The Design And Evolution of C++</i>. Addison
                Wesley, Reading, MA, 1995, ISBN 0-201-54330-3, Section
                16.9.1.</li>
              </ol>

              <h2>Footnotes</h2>

              <p><a name="footnote1" id="footnote1">1</a> Probably the
              greatest impediment to a solution in Cargill's case was an
              unfortunate combination of choices on his part: the interface
              he chose for his container was incompatible with his particular
              demands for safety. By changing either one he might have solved
              the problem.</p>

              <p><a name="footnote2" id="footnote2">2</a> It is usually
              inadvisable to throw an exception from a destructor in C++,
              since the destructor may itself be called during the
              stack-unwinding caused by another exception. If the second
              exception is allowed to propagate beyond the destructor, the
              program is immediately terminated.</p>

              <p><a name="footnote3" id="footnote3">3</a> In practice of
              course, this function would make an extremely poor random
              sequence generator!</p>

              <p><a name="footnote4" id="footnote4">4</a> It is worth noting
              that mutating algorithms usually cannot provide the
              <i>strong</i> guarantee: to roll back a modified element of a
              range, it must be set back to its previous value using
              <code>operator=</code>, which itself might throw. In the C++
              standard library, there are a few exceptions to this rule,
              whose rollback behavior consists only of destruction:
              <code>uninitialized_copy</code>,
              <code>uninitialized_fill</code>, and
              <code>uninitialized_fill_n</code>.</p>

              <p><a name="footnote5" id="footnote5">5</a> All type parameters
              supplied by clients of the C++ standard library are required
              not to throw from their destructors. In return, all components
              of the C++ standard library provide at least the <i>basic</i>
              guarantee.</p>

              <p><a name="footnote6" id="footnote6">6</a> Similar
              arrangements might have been made in the C++ standard for many
              of the mutating algorithms, but were never considered due to
              time constraints on the standardization process.</p>

              <p><a name="footnote7" id="footnote7">7</a> Associative
              containers whose <code>Compare</code> object might throw an
              exception when copied cannot use this technique, since the swap
              function might fail.</p>

              <p><a name="footnote8" id="footnote8">8</a> This suggests
              another potential use for the oft-wished-for but as yet unseen
              <code>container_traits&lt;&gt;</code> template: automated
              container selection to meet exception-safety constraints.</p>

              <p><a name="footnote9" id="footnote9">9</a> One might be
              tempted to surround the erase operation with a
              <code>try</code>/<code>catch</code> block to reduce the
              requirements on <code>set&lt;T&gt;</code> and the problems that
              arise in case of an exception, but in the end that just begs
              the question. First, erase just failed and in this case there
              are no viable alternative ways to produce the necessary result.
              Second and more generally, because of the variability of its
              type parameters a generic component can seldom be assured that
              any alternatives will succeed.</p>

              <p><a name="footnote10" id="footnote10">10</a> The prevalent
              philosophy in the design of STL was that functionality that
              wasn't essential to all uses should be left out in favor of
              efficiency, as long as that functionality could be obtained
              when needed by adapting the base components. This departs from
              that philosophy, but it would be difficult or impossible to
              obtain even the <i>basic</i> guarantee by adapting a base
              component that doesn't already have it.</p>

              <p><a name="footnote11" id="footnote11">11</a> An excellent
              discussion on how to fortify memory subsystems can be found in:
              Steve Maguire, Writing Solid Code, Microsoft Press, Redmond,
              WA, 1993, ISBN 1-55615- 551-4.</p>

              <p><a name="footnote12" id="footnote12">12</a> Note that this
              technique requires that the operation being tested be
              exception-neutral. If the operation ever tries to recover from
              an exception and proceed, the throw counter will be negative,
              and subsequent operations that might fail will not be tested
              for exception-safety.</p>

              <p><a name="footnote13" id="footnote13">13</a> The changes to
              the draft standard which introduced exception-safety were made
              late in the process, when amendments were likely to be rejected
              solely on the basis of the number of altered words.
              Unfortunately, the result compromises clarity somewhat in favor
              of brevity. Greg Colvin was responsible for the clever
              language-lawyering needed to minimize the extent of these
              changes.</p>
            </div>
          </div>
        </div>
      </div>

      <div id="sidebar">
        <!--#include virtual="/common/sidebar-common.html" -->
        <!--#include virtual="/common/sidebar-community.html" -->
      </div>

      <div class="clear"></div>
    </div>
  </div>

  <div id="footer">
    <div id="footer-left">
      <div id="revised">
        <p>Revised $Date$</p>
      </div>

      <div id="copyright">
        <p>Copyright David Abrahams 2001.</p>
      </div><!--#include virtual="/common/footer-license.html" -->
    </div>

    <div id="footer-right">
      <!--#include virtual="/common/footer-banners.html" -->
    </div>

    <div class="clear"></div>
  </div>
</body>
</html>
